package leecode.array.二分查找问题;

/**
 * https://leetcode-cn.com/problems/search-a-2d-matrix-ii/
 */
public class SearchMatrixII {
    /**
     * 这个不能使用行列二分来做、假设使用会有什么问题：
     *
     * 使用行二分，假设找到了最后一个小于 target的行首元素，那么顺着这一行二分查找
     * 如果找不到就确定target不在数组中吗？
     *
     * 其实不是，假设行二分定位是第3行，但是target却在第2行，此时第二行首元素 < 第3行首元素 < target
     * 顺着第三行找肯定就返回false了，但是target在数组中。比如{{1,4},{2,5}} target=5就不行了
     *
     * SearchMatrix这个题的条件不一样。
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length <= 0) {
            return false;
        }
        int rowIndex = 0;
        int colIndex = matrix[0].length - 1;
        while (rowIndex < matrix.length && colIndex >= 0) {
            int temp = matrix[rowIndex][colIndex];
            if (temp == target) {
                return true;
            } else if (target > temp) {
                rowIndex++;
            } else {
                colIndex--;
            }
        }
        return false;
    }
}
